public class MyLIst0 {
    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }

    }
    //BM7 链表中环的入口结点
    public class Solution {
        public ListNode EntryNodeOfLoop(ListNode head) {
            if (head == null || head.next == null) {
                return null;
            }
            ListNode slow = head.next;
            ListNode fast = head.next.next;
            while (fast != slow) {
                if(fast == null || fast.next == null){
                    return null;
                }
                slow = slow.next;
                fast = fast.next.next;
            }
            slow = head;
            while(fast != slow){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    //BM8 链表中倒数最后k个结点
    public class Solution1 {
        public ListNode FindKthToTail (ListNode head, int k) {
            // write code here
            if(head == null || k == 0){
                return null;
            }
            ListNode slow = head;
            ListNode fast = head;
            for(int i = 0;i < k - 1;i++){
                if(fast.next == null){
                    return null;
                }
                fast = fast.next;
            }
            while(fast.next != null){
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }
    //BM9 两个链表的第一个公共结点
    public class Solution2 {
        public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
            if(head1 == null || head2 == null){
                return null;
            }
            ListNode cur1 = head1;
            ListNode cur2 = head2;
            while(cur1 != cur2){
                if(cur1 == null){
                    cur1 = head2;
                }else {
                    cur1 = cur1.next;
                }
                if(cur2 == null){
                    cur2 = head1;
                }else  {
                    cur2 = cur2.next;
                }
            }
            return cur1;
        }
    }
    //BM11 链表相加(二)
    public class Solution3 {
        public ListNode addInList (ListNode head1, ListNode head2) {
            // write code here
            if(head1 == null){
                return head2;
            }
            if(head2 == null){
                return head1;
            }
            head1 = reverseList(head1);
            head2 = reverseList(head2);
            ListNode cur1 = head1;
            ListNode cur2 = head2;
            ListNode head = new ListNode(-1);
            ListNode cur = head;
            int tmp = 0;
            while(cur1 != null || cur2 != null){
                int val = tmp;
                if(cur1 != null){
                    val += cur1.val;
                    cur1 = cur1.next;
                }
                if(cur2 != null){
                    val += cur2.val;
                    cur2 = cur2.next;
                }
                tmp = val / 10;
                cur.next = new ListNode(val % 10);
                cur = cur.next;
            }
            if(tmp > 0){
                cur.next = new ListNode(tmp);
            }
            head = reverseList(head.next);
            return head;
        }
        public ListNode reverseList(ListNode head) {
            if(head == null){
                return null;
            }
            ListNode cur = head.next;
            head.next = null;
            while(cur != null){
                ListNode curNext = cur.next;
                cur.next = head;
                head = cur;
                cur = curNext;
            }
            return head;
        }
    }
}
